package hot100;


/*
 * Author：江松
 * Date：2023/4/22 10:20
 *
 搜索旋转排序数组：
 1，二分查找
 6 7 1 2 3 4 5
 3 4 5 6 7 1 2
 基本思路是在有序部分二分查找,如果不是该部分不有序就去另外一半区间
 如果al<=amid说明左区间是有序的，如果al<=k<amid在左区间查找，反之再右区间查找
 如果al>amid说明右区间有序， 如果amid<k<=ar右区间，反之左区间
 */

public class Main33 {
    public int search(int[] a, int k) {
        int l=0,r=a.length-1;
        while(l<=r){
            int mid=((r-l)>>1)+l;
            if(a[mid]==k)return mid;
            if(a[l]<=a[mid]){
                if(a[l]<=k&&a[mid]>k)r=mid-1;
                else l=mid+1;
            }else{
                if(a[r]>=k&&a[mid]<k)l=mid+1;
                else r=mid-1;
            }
        }
        return -1;
    }
}
